{
 "metadata": {
  "name": "",
  "signature": "sha256:bdcf5769a1b41042d99a824bed6e68a1295f6f269d2ce8dbdf471a938b772624"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Ensemble of Decision Trees"
     ]
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "*By Parijat Mazumdar (GitHub ID: [mazumdarparijat](https://github.com/mazumdarparijat))*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This notebook illustrates the use of [Random Forests](http://en.wikipedia.org/wiki/Random_forest) in Shogun for classification and regression. We will understand the functioning of Random Forests, discuss about the importance of its various parameters and appreciate the usefulness of this learning method.  "
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "What is Random Forest?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Random Forest is an ensemble learning method in which a collection of decision trees are grown during training and the combination of the outputs of all the individual trees are considered during testing or application. The strategy for combination can be varied but generally, in case of classification, the mode of the output classes is used and, in case of regression, the mean of the outputs is used. The randomness in the method, as the method's name suggests, is infused mainly by the random subspace sampling done while training individual trees. While choosing the best split during tree growing, only a small randomly chosen subset of all the features is considered. The subset size is a user-controlled parameter and is usually the square root of the total number of available features. The purpose of the random subset sampling method is to decorrelate the individual trees in the forest, thus making the overall model more generic; i.e. decrease the variance without increasing the bias (see [bias-variance trade-off](http://en.wikipedia.org/wiki/Bias%E2%80%93variance_dilemma)). The purpose of Random Forest, in summary, is to reduce the generalization error of the model as much as possible.    "
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Random Forest vs Decision Tree"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In this section, we will appreciate the importance of training a Random Forest over a single decision tree. In the process, we will also learn how to use Shogun's [Random Forest class](http://www.shogun-toolbox.org/doc/en/latest/classshogun_1_1CRandomForest.html). For this purpose, we will use the [letter recognition dataset](https://archive.ics.uci.edu/ml/datasets/Letter+Recognition). This dataset contains pixel information (16 features) of 20000 samples of the English alphabet. This is a 26-class classification problem where the task is to predict the alphabet given the 16 pixel features. We start by loading the training dataset."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from modshogun import CSVFile,RealFeatures,MulticlassLabels\n",
      "\n",
      "def load_file(feat_file,label_file):\n",
      "    feats=RealFeatures(CSVFile(feat_file))\n",
      "    labels=MulticlassLabels(CSVFile(label_file))\n",
      "    return (feats, labels)\n",
      "\n",
      "trainfeat_file='../../../../data/uci/letter/train_fm_letter.dat'\n",
      "trainlab_file='../../../../data/uci/letter/train_label_letter.dat'\n",
      "train_feats,train_labels=load_file(trainfeat_file,trainlab_file)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Next, we decide the parameters of our Random Forest. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from modshogun import RandomForest, MajorityVote\n",
      "from numpy import array\n",
      "\n",
      "def setup_random_forest(num_trees,rand_subset_size,combination_rule,feature_types):\n",
      "    rf=RandomForest(rand_subset_size,num_trees)\n",
      "    rf.set_combination_rule(combination_rule)\n",
      "    rf.set_feature_types(feature_types)\n",
      "\n",
      "    return rf\n",
      "\n",
      "comb_rule=MajorityVote()\n",
      "feat_types=array([False]*16)\n",
      "rand_forest=setup_random_forest(10,4,comb_rule,feat_types)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In the above code snippet, we decided to create a forest using 10 trees in which each split in individual trees will be using a randomly chosen subset of 4 features. Note that 4 here is the square root of the total available features (16) and is hence the usually chosen value as mentioned in the introductory paragraph. The strategy for combination chosen is [Majority Vote](http://www.shogun-toolbox.org/doc/en/latest/classshogun_1_1CMajorityVote.html) which, as the name suggests, chooses the mode of all the individual tree outputs. The given features are all continuous in nature and hence feature types are all set false (i.e. not nominal). Next, we train our Random Forest and use it to classify letters in our test dataset.  "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# train forest\n",
      "rand_forest.set_labels(train_labels)\n",
      "rand_forest.train(train_feats)\n",
      "\n",
      "# load test dataset\n",
      "testfeat_file='../../../../data/uci/letter/test_fm_letter.dat'\n",
      "testlab_file='../../../../data/uci/letter/test_label_letter.dat'\n",
      "test_feats,test_labels=load_file(testfeat_file,testlab_file)\n",
      "\n",
      "# apply forest\n",
      "output_rand_forest_train=rand_forest.apply_multiclass(train_feats)\n",
      "output_rand_forest_test=rand_forest.apply_multiclass(test_feats)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We have with us the labels predicted by our Random Forest model. Let us also get the predictions made by a single tree. For this purpose, we train a [CART-flavoured decision tree](http://www.shogun-toolbox.org/doc/en/latest/classshogun_1_1CCARTree.html)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from modshogun import CARTree, PT_MULTICLASS\n",
      "\n",
      "def train_cart(train_feats,train_labels,feature_types,problem_type):\n",
      "    c=CARTree(feature_types,problem_type,2,False)\n",
      "    c.set_labels(train_labels)\n",
      "    c.train(train_feats)\n",
      "    \n",
      "    return c\n",
      "\n",
      "# train CART\n",
      "cart=train_cart(train_feats,train_labels,feat_types,PT_MULTICLASS)\n",
      "\n",
      "# apply CART model\n",
      "output_cart_train=cart.apply_multiclass(train_feats)\n",
      "output_cart_test=cart.apply_multiclass(test_feats)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "With both results at our disposal, let us find out which one is better."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from modshogun import MulticlassAccuracy\n",
      "\n",
      "accuracy=MulticlassAccuracy()\n",
      "\n",
      "rf_train_accuracy=accuracy.evaluate(output_rand_forest_train,train_labels)*100\n",
      "rf_test_accuracy=accuracy.evaluate(output_rand_forest_test,test_labels)*100\n",
      "\n",
      "cart_train_accuracy=accuracy.evaluate(output_cart_train,train_labels)*100\n",
      "cart_test_accuracy=accuracy.evaluate(output_cart_test,test_labels)*100\n",
      "\n",
      "print('Random Forest training accuracy : '+str(round(rf_train_accuracy,3))+'%')\n",
      "print('CART training accuracy : '+str(round(cart_train_accuracy,3))+'%')\n",
      "print\n",
      "print('Random Forest test accuracy : '+str(round(rf_test_accuracy,3))+'%')\n",
      "print('CART test accuracy : '+str(round(cart_test_accuracy,3))+'%')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "As it is clear from the results above, we see a significant improvement in the predictions. The reason for the improvement is clear when one looks at the training accuracy. The single decision tree was over-fitting on the training dataset and hence was not generic. Random Forest on the other hand appropriately trades off training accuracy for the sake of generalization of the model. Impressed already? Let us now see what happens if we increase the number of trees in our forest."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Random Forest parameters : Number of trees and random subset size "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In the last section, we trained a forest of 10 trees. What happens if we make our forest with 20 trees? Let us try to answer this question in a generic way."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def get_rf_accuracy(num_trees,rand_subset_size):\n",
      "    rf=setup_random_forest(num_trees,rand_subset_size,comb_rule,feat_types)\n",
      "    rf.set_labels(train_labels)\n",
      "    rf.train(train_feats)\n",
      "    out_test=rf.apply_multiclass(test_feats)\n",
      "    acc=MulticlassAccuracy()\n",
      "    return acc.evaluate(out_test,test_labels)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The method above takes the number of trees and subset size as inputs and returns the evaluated accuracy as output. Let us use this method to get the accuracy for different number of trees keeping the subset size constant at 4."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import matplotlib.pyplot as plt\n",
      "% matplotlib inline\n",
      "\n",
      "num_trees4=[5,10,20,50,100]\n",
      "rf_accuracy_4=[round(get_rf_accuracy(i,4)*100,3) for i in num_trees4]\n",
      "\n",
      "print('Random Forest accuracies (as %) :' + str(rf_accuracy_4))\n",
      "\n",
      "# plot results\n",
      "\n",
      "x4=[1]\n",
      "y4=[86.48] # accuracy for single tree-CART\n",
      "x4.extend(num_trees4)\n",
      "y4.extend(rf_accuracy_4)\n",
      "plt.plot(x4,y4,'--bo')\n",
      "plt.xlabel('Number of trees')\n",
      "plt.ylabel('Multiclass Accuracy (as %)')\n",
      "plt.xlim([0,110])\n",
      "plt.ylim([85,100])\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "heading",
     "level": 6,
     "metadata": {},
     "source": [
      "NOTE : The above code snippet takes about a minute to execute. Please wait patiently."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We see from the above plot that the accuracy of the model keeps on increasing as we increase the number of trees on our Random Forest and eventually satarates at some value. Extrapolating the above plot qualitatively, the saturation value will be somewhere around 96.5%. The jump of accuracy from 86.48% for a single tree to 96.5% for a Random Forest with about 100 trees definitely highlights the importance of the Random Forest algorithm.\n",
      "\n",
      "The inevitable question at this point is whether it is possible to achieve higher accuracy saturation by working with lesser (or greater) random feature subset size. Let us figure this out by repeating the above procedure for random subset size as 2 and 8."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# subset size 2\n",
      "\n",
      "num_trees2=[10,20,50,100]\n",
      "rf_accuracy_2=[round(get_rf_accuracy(i,2)*100,3) for i in num_trees2]\n",
      "\n",
      "print('Random Forest accuracies (as %) :' + str(rf_accuracy_2))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# subset size 8\n",
      "\n",
      "num_trees8=[5,10,50,100]\n",
      "rf_accuracy_8=[round(get_rf_accuracy(i,8)*100,3) for i in num_trees8]\n",
      "\n",
      "print('Random Forest accuracies (as %) :' + str(rf_accuracy_8))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "heading",
     "level": 6,
     "metadata": {},
     "source": [
      "NOTE : The above code snippets take about a minute each to execute. Please wait patiently."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Let us plot all the results together and then comprehend the results."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x2=[1]\n",
      "y2=[86.48]\n",
      "x2.extend(num_trees2)\n",
      "y2.extend(rf_accuracy_2)\n",
      "\n",
      "x8=[1]\n",
      "y8=[86.48]\n",
      "x8.extend(num_trees8)\n",
      "y8.extend(rf_accuracy_8)\n",
      "\n",
      "plt.plot(x2,y2,'--bo',label='Subset Size = 2')\n",
      "plt.plot(x4,y4,'--r^',label='Subset Size = 4')\n",
      "plt.plot(x8,y8,'--gs',label='Subset Size = 8')\n",
      "plt.xlabel('Number of trees')\n",
      "plt.ylabel('Multiclass Accuracy (as %) ')\n",
      "plt.legend(bbox_to_anchor=(0.92,0.4))\n",
      "plt.xlim([0,110])\n",
      "plt.ylim([85,100])\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "As we can see from the above plot, the subset size does not have a major impact on the saturated accuracy obtained in this particular dataset. While this is true in many datasets, this is not a generic observation. In some datasets, the random feature sample size does have a measurable impact on the test accuracy. A simple strategy to find the optimal subset size is to use cross-validation. But with Random Forest model, there is actually no need to perform cross-validation. Let us see how in the next section.  "
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Out-of-bag error"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The individual trees in a Random Forest are trained over data vectors randomly chosen with replacement. As a result, some of the data vectors are left out of training by each of the individual trees. These vectors form the out-of-bag (OOB) vectors of the corresponding trees. A data vector can be part of OOB classes of multiple trees. While calculating OOB error, a data vector is applied to only those trees of which it is a part of OOB class and the results are combined. This combined result averaged over similar estimate for all other vectors gives the OOB error. The OOB error is an estimate of the generalization bound of the Random Forest model. Let us see how to compute this OOB estimate in Shogun.  "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "rf=setup_random_forest(100,2,comb_rule,feat_types)\n",
      "rf.set_labels(train_labels)\n",
      "rf.train(train_feats)\n",
      "    \n",
      "# set evaluation strategy\n",
      "eval=MulticlassAccuracy()\n",
      "oobe=rf.get_oob_error(eval)\n",
      "\n",
      "print('OOB accuracy : '+str(round(oobe*100,3))+'%')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The above OOB accuracy calculated is found to be slighly less than the test error evaluated in the previous section (see plot for num_trees=100 and rand_subset_size=2). This is because of the fact that the OOB estimate depicts the expected error for any generalized set of data vectors. It is only natural that for some set of vectors, the actual accuracy is slightly greater than the OOB estimate while in some cases the accuracy observed in a bit lower.\n",
      "\n",
      "Let us now apply the Random Forest model to the [wine dataset](https://archive.ics.uci.edu/ml/datasets/Wine). This dataset is different from the previous one in the sense that this dataset is small and has no separate test dataset. Hence OOB (or equivalently cross-validation) is the only viable strategy available here. Let us read the dataset first. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "trainfeat_file='../../../../data/uci/wine/fm_wine.dat'\n",
      "trainlab_file='../../../../data/uci/wine/label_wine.dat'\n",
      "train_feats,train_labels=load_file(trainfeat_file,trainlab_file)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Next let us find out the appropriate feature subset size. For this we will make use of OOB error."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import matplotlib.pyplot as plt\n",
      "\n",
      "def get_oob_errors_wine(num_trees,rand_subset_size):\n",
      "    feat_types=array([False]*13)\n",
      "    rf=setup_random_forest(num_trees,rand_subset_size,MajorityVote(),feat_types)\n",
      "    rf.set_labels(train_labels)\n",
      "    rf.train(train_feats)\n",
      "    eval=MulticlassAccuracy()\n",
      "    return rf.get_oob_error(eval)    \n",
      "\n",
      "size=[1,2,4,6,8,10,13]\n",
      "oobe=[round(get_oob_errors_wine(400,i)*100,3) for i in size]\n",
      "\n",
      "print('Out-of-box Accuracies (as %) : '+str(oobe))\n",
      "\n",
      "plt.plot(size,oobe,'--bo')\n",
      "plt.xlim([0,14])\n",
      "plt.xlabel('Random subset size')\n",
      "plt.ylabel('Multiclass accuracy')\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "From the above plot it is clear that subset size of 2 or 3 produces maximum accuracy for wine classification. At this value of subset size, the expected classification accuracy is of the model is 98.87%. Finally, as a sanity check, let us plot the accuracy vs number of trees curve to ensure that 400 is indeed a sufficient value ie. the oob error saturates before 400."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "size=[50,100,200,400,600]\n",
      "oobe=[round(get_oob_errors_wine(i,2)*100,3) for i in size]\n",
      "\n",
      "print('Out-of-box Accuracies (as %) : '+str(oobe))\n",
      "\n",
      "plt.plot(size,oobe,'--bo')\n",
      "plt.xlim([40,650])\n",
      "plt.ylim([95,100])\n",
      "plt.xlabel('Number of trees')\n",
      "plt.ylabel('Multiclass accuracy')\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We see from the above plot that the accuracy remains constant beyond 100. Hence 400 is a sufficient value. In-fact, values just above 100 would have been ideal because of the lower training time associated with them. "
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "References"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "[1] Bache, K. & Lichman, M. (2013). UCI Machine Learning Repository [http://archive.ics.uci.edu/ml]. Irvine, CA: University of California, School of Information and Computer Science\n",
      "\n",
      "[2] Leo Breiman. 2001. Random Forests. Mach. Learn. 45, 1 (October 2001), 5-32. DOI=10.1023/A:1010933404324 http://dx.doi.org/10.1023/A:1010933404324 "
     ]
    }
   ],
   "metadata": {}
  }
 ]
}